#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : ReverseLinkedList2.py
# @Time    : 2020/9/14 21:03
# @Description:


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        """
        Reverse a linked list from position m to n. Do it in one-pass.

        Note: 1 ≤ m ≤ n ≤ length of list.
        
        Example:
            Input: 1->2->3->4->5->NULL, m = 2, n = 4
            Output: 1->4->3->2->5->NULL

        :param head:
        :param m:
        :param n:
        :return:
        """
        if not head:
            return None
        left, right = head, head
        stop = False

        def recurseAndReverse(right, m, n):
            nonlocal left, stop
            if n == 1:
                return
            right = right.next
            if m > 1:
                left = left.next

            recurseAndReverse(right, m - 1, n - 1)
            if left == right or right.next == left:
                stop = True

            if not stop:
                left.val, right.val = right.val, left.val
                left = left.next

        recurseAndReverse(right, m, n)
        return head

    def reverseBetween2(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head:
            return None
        cur, prev = head, None
        while m > 1:
            prev = cur
            cur = cur.next
            m, n = m - 1, n - 1
        tail, con = cur, prev
        while n:
            third = cur.next
            cur.next = prev
            prev = cur
            cur = third
            n -= 1
        if con:
            con.next = prev
        else:
            head = prev
        tail.next = cur
        return head


if __name__ == '__main__':
    S = Solution()
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    m = 2
    n = 4
    S.reverseBetween(head, m, n)
    print('done')
